/**
  @(#)$Id: AL_TreeNodeBinSearchSeq.h 86 2013-10-17 11:56:44Z xiaoting $
  @brief	Each of the data structure corresponds to a data node storage unit, this storage unit is called storage node, the node can 
  also be referred to.
	
  The related concepts of tree node 
  1.degree		degree node: A node of the subtree containing the number is called the node degree;
  2.leaf			leaf nodes or terminal nodes: degree 0 are called leaf nodes;
  3.branch		non-terminal node or branch node: node degree is not 0;
  4.parent		parent node or the parent node: If a node contains a child node, this node is called its child node's parent;
  5.child			child node or child node: A node subtree containing the root node is called the node's children;
  6.slibing		sibling nodes: nodes with the same parent node is called mutual sibling;
  7.ancestor		ancestor node: from the root to the node through all the nodes on the branch;
  8.descendant	descendant nodes: a node in the subtree rooted at any node is called the node's descendants.

  ////////////////////////////////Binary Search Tree(Binary Sort Tree)//////////////////////////////////////////
  Binary Search Tree(Binary Sort Tree), also known as a binary search tree, also known as binary search tree. It is either empty 
  tree; or a binary tree with the following properties: (1) If the left subtree is not empty, then all nodes in the left sub-tree, 
  the values ​​are less than the value of its root; (2) if the right subtree is not empty, then all nodes in the right subtree are 
  greater than the value of the value of its root; (3) left and right subtrees are also binary sort tree;

  ////////////////////////////////Binary Tree//////////////////////////////////////////
  In computer science, a binary tree is that each node has at most two sub-trees ordered tree. Usually the root of the subtree is 
  called "left subtree" (left subtree) and the "right subtree" (right subtree). Binary tree is often used as a binary search tree 
  and binary heap or a binary sort tree. Binary tree each node has at most two sub-tree (does not exist a degree greater than two 
  nodes), left and right sub-tree binary tree of the points, the order can not be reversed. Binary i-th layer of at most 2 power 
  nodes i -1; binary tree of depth k at most 2 ^ (k) -1 nodes; for any binary tree T, if it is the terminal nodes (i.e. leaf nodes) 
  is, the nodes of degree 2 is, then = + 1.

  ////////////////////////////////Sequential storage structure//////////////////////////////////////////
  Using a set of addresses in the computer storage unit sequentially stores continuous linear form of individual data elements, called 
  the linear order of the table storage structure.

  Sequential storage structure is a type of a storage structure, the structure is the logically adjacent nodes stored in the physical 
  location of the adjacent memory cells, the logical relationship between nodes from the storage unit to reflect the adjacency. 
  Storage structure thus obtained is stored in order structure, usually by means of sequential storage structure computer programming 
  language (e.g., c / c) of the array to describe.

  The main advantage of the storage structure in order to save storage space, because the allocation to the data storage unit storing 
  all nodes with data (without regard to c / c language in the array size required for the case), the logical relationship between 
  the nodes does not take additional storage space. In this method, the node can be realized on a random access, that is, each node 
  corresponds to a number, the number can be calculated directly from the node out of the memory address. However, the main 
  disadvantage of sequential storage method is easy to modify the node insert, delete operations, may have to move a series of nodes.
          
  Benefits:
	Random Access table elements. 
  Disadvantages: 
    insert and delete operations need to move elements.

  @Author $Author: xiaoting $
  @Date $Date: 2013-10-17 19:56:44 +0800 (周四, 17 十月 2013) $
  @Revision $Revision: 86 $
  @URL $URL: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeNodeBinSearchSeq.h $
  @Header $Header: https://svn.code.sf.net/p/xiaoting/game/trunk/MyProject/AL_DataStructure/groupinc/AL_TreeNodeBinSearchSeq.h 86 2013-10-17 11:56:44Z xiaoting $
 */

#ifndef CXX_AL_TREENODEBINSEARCHSEQ_H
#define CXX_AL_TREENODEBINSEARCHSEQ_H

#ifndef CXX_AL_LISTSEQ_H
#include "AL_ListSeq.h"
#endif

#ifndef CXX_AL_QUEUESEQ_H
#include "AL_QueueSeq.h"
#endif


///////////////////////////////////////////////////////////////////////////
//			AL_TreeNodeBinSearchSeq
///////////////////////////////////////////////////////////////////////////

template<typename T, typename KEY> class AL_TreeBinSearchSeq;

template<typename T, typename KEY> 
class AL_TreeNodeBinSearchSeq
{
friend class AL_TreeBinSearchSeq<T, KEY>;

public:
	/**
	* Destruction
	*
	* @param
	* @return
	* @note
	* @attention 
	*/
	~AL_TreeNodeBinSearchSeq();
	
	/**
	* GetLevel
	*
	* @param
	* @return	DWORD
	* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	* @attention 
	*/
	DWORD GetLevel() const;

	/**
	* SetLevel
	*
	* @param	DWORD dwLevel <IN>
	* @return	
	* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	* @attention 
	*/
	VOID SetLevel(DWORD dwLevel);

	/**
	* GetWeight
	*
	* @param
	* @return	DWORD
	* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
	* @attention only be used in Huffman tree...
	*/
	DWORD GetWeight() const;

	/**
	* SetWeight
	*
	* @param	DWORD dwWeight <IN>
	* @return	
	* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
	* @attention only be used in Huffman tree...
	*/
	VOID SetWeight(DWORD dwWeight);

	/**
	* GetData
	*
	* @param
	* @return	T
	* @note 
	* @attention 
	*/
	T GetData() const;

	/**
	* SetData
	*
	* @param	const T& tData <IN>
	* @return	
	* @note 
	* @attention 
	*/
	VOID SetData(const T& tData);

	/**
	* GetKey
	*
	* @param
	* @return	KEY
	* @note 
	* @attention 
	*/
	KEY GetKey() const;

	/**
	* SetKey
	*
	* @param	const KEY& tKey <IN>
	* @return	
	* @note 
	* @attention 
	*/
	VOID SetKey(const KEY& tKey);

	/**
	* GetParent
	*
	* @param	
	* @return	AL_TreeNodeBinSearchSeq<T, KEY>*	
	* @note parent node pointer, not to manager memory
	* @attention 
	*/
	AL_TreeNodeBinSearchSeq<T, KEY>*	GetParent() const;

	/**
	* SetParent
	*
	* @param	DWORD dwIndex <IN>
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pParent <IN>
	* @return	BOOL
	* @note parent node pointer, not to manager memory
	* @attention as the child to set the parent at the index (from the left of parent's child ) [0x00: left child, 0x01: right child]
	*/
	BOOL SetParent(DWORD dwIndex, AL_TreeNodeBinSearchSeq<T, KEY>* pParent);

	/**
	* SetParentLeft
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pParent <IN>
	* @return	BOOL
	* @note parent node pointer, not to manager memory
	* @attention as the child to set the parent at the left (from the left of parent's child )
	*/
	BOOL SetParentLeft(AL_TreeNodeBinSearchSeq<T, KEY>* pParent);

	/**
	* SetParentRight
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pParent <IN>
	* @return	BOOL
	* @note parent node pointer, not to manager memory
	* @attention as the child to set the parent at the right (from the right of parent's child )
	*/
	BOOL SetParentRight(AL_TreeNodeBinSearchSeq<T, KEY>* pParent);

	/**
	* Insert
	*
	* @param	DWORD dwIndex <IN>
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild <IN> 
	* @return	BOOL
	* @note inset the const AL_TreeNodeBinSearchSeq<T, KEY>*  into the child notes at the position [0x00: left child, 0x01: right child]
	* @attention
	*/
	BOOL Insert(DWORD dwIndex, AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild);

	/**
	* InsertLeft
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild <IN> 
	* @return	BOOL
	* @note inset the const AL_TreeNodeBinSearchSeq<T, KEY>*  into the child notes at the left
	* @attention
	*/
	BOOL InsertLeft(AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild);

	/**
	* InsertRight
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild <IN> 
	* @return	BOOL
	* @note inset the const AL_TreeNodeBinSearchSeq<T, KEY>*  into the child notes at the right
	* @attention
	*/
	BOOL InsertRight(AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild);
	
	/**
	* RemoveParent
	*
	* @param
	* @return	BOOL
	* @note remove the parent note
	* @attention
	*/
	BOOL RemoveParent();

	/**
	* Remove
	*
	* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pRemoveChild <IN>
	* @return	BOOL
	* @note remove the notes in the child
	* @attention
	*/
	BOOL Remove(AL_TreeNodeBinSearchSeq<T, KEY>* pRemoveChild);

	/**
	* Remove
	*
	* @param	DWORD dwIndex <IN>
	* @return	BOOL
	* @note remove the child notes at the position [0x00: left child, 0x01: right child]
	* @attention
	*/
	BOOL Remove(DWORD dwIndex);

	/**
	* RemoveLeft
	*
	* @param
	* @return	BOOL
	* @note remove the child notes at the left
	* @attention
	*/
	BOOL RemoveLeft();

	/**
	* RemoveRight
	*
	* @param
	* @return	BOOL
	* @note remove the child notes at the right
	* @attention
	*/
	BOOL RemoveRight();

	/**
	* GetChildLeft
	*
	* @param	
	* @return	AL_TreeNodeBinSearchSeq<T, KEY>*
	* @note 
	* @attention
	*/
	AL_TreeNodeBinSearchSeq<T, KEY>* GetChildLeft() const;

	/**
	* GetChildRight
	*
	* @param	
	* @return	AL_TreeNodeBinSearchSeq<T, KEY>*
	* @note 
	* @attention
	*/
	AL_TreeNodeBinSearchSeq<T, KEY>* GetChildRight() const;
	
	/**
	* GetDegree
	*
	* @param
	* @return	DWORD
	* @note degree node: A node of the subtree containing the number is called the node degree;
	* @attention 
	*/
	DWORD GetDegree() const;

	/**
	* IsLeaf
	*
	* @param
	* @return	BOOL
	* @note leaf nodes or terminal nodes: degree 0 are called leaf nodes;
	* @attention 
	*/
	BOOL IsLeaf() const;

	/**
	* IsBranch
	*
	* @param
	* @return	BOOL
	* @note non-terminal node or branch node: node degree is not 0;
	* @attention 
	*/
	BOOL IsBranch() const;

	/**
	* IsParent
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pChild <IN>
	* @return	BOOL
	* @note parent node or the parent node: If a node contains a child node, this node is called its child 
	* @attention 
	*/
	BOOL IsParent(const AL_TreeNodeBinSearchSeq<T, KEY>* pChild) const;

	/**
	* GetSibling
	*
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling <OUT>
	* @return	BOOL
	* @note sibling nodes: nodes with the same parent node is called mutual sibling;
	* @attention 
	*/
	BOOL GetSibling(AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling) const;

	/**
	* GetAncestor
	*
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention 
	*/
	BOOL GetAncestor(AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor) const;

	/**
	* GetDescendant
	*
	* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant <OUT>
	* @return	BOOL
	* @note ancestor node: from the root to the node through all the nodes on the branch;
	* @attention 
	*/
	BOOL GetDescendant(AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant) const;

	/**
	* Clear
	*
	* @param
	* @return	VOID
	* @note
	* @attention 
	*/
	VOID Clear();

protected:
private:

	/**
	* Construction
	*
	* @param
	* @return
	* @note private the Construction, avoid the others use it
	* @attention
	*/
	AL_TreeNodeBinSearchSeq();
	
	/**
	* Construction
	*
	* @param	const T& tData <IN>
	* @param	const KEY& tKey <IN>
	* @return
	* @note
	* @attention private the Construction, avoid the others use it
	*/
	AL_TreeNodeBinSearchSeq(const T& tData, const KEY& tKey);

	/**
	*Copy Construct
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>& cAL_TreeNodeBinSearchSeq
	* @return
	*/
	AL_TreeNodeBinSearchSeq(const AL_TreeNodeBinSearchSeq<T, KEY>& cAL_TreeNodeBinSearchSeq);

	/**
	*Assignment
	*
	* @param	const AL_TreeNodeBinSearchSeq<T, KEY>& cAL_TreeNodeBinSearchSeq
	* @return	AL_TreeNodeBinSearchSeq<T, KEY>&
	*/
	AL_TreeNodeBinSearchSeq<T, KEY>& operator = (const AL_TreeNodeBinSearchSeq<T, KEY>& cAL_TreeNodeBinSearchSeq);

public:
protected:
private:
	DWORD								m_dwLevel;				//Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
	DWORD								m_dwWeight;				//If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
																//only be used in Huffman tree...

	T									m_tData;					//the friend class can use it directly
	KEY									m_tKey;					//the key for binary search (sort)

	AL_TreeNodeBinSearchSeq<T, KEY>*				m_pParent;				//Parent position
	AL_TreeNodeBinSearchSeq<T, KEY>*				m_pChildLeft;			//Child tree node left
	AL_TreeNodeBinSearchSeq<T, KEY>*				m_pChildRight;			//Child tree node right
};

///////////////////////////////////////////////////////////////////////////
//			AL_TreeNodeBinSearchSeq
///////////////////////////////////////////////////////////////////////////

/**
* Construction
*
* @param
* @return
* @note private the Construction, avoid the others use it
* @attention
*/
template<typename T, typename KEY> 
AL_TreeNodeBinSearchSeq<T, KEY>::AL_TreeNodeBinSearchSeq():
m_dwLevel(0x00),
m_dwWeight(0x00),
m_pParent(NULL),
m_pChildLeft(NULL),
m_pChildRight(NULL)
{

}

/**
* Construction
*
* @param	const T& tData <IN>
* @param	const KEY& tKey <IN>
* @return
* @note
* @attention private the Construction, avoid the others use it
*/
template<typename T, typename KEY> 
AL_TreeNodeBinSearchSeq<T, KEY>::AL_TreeNodeBinSearchSeq(const T& tData, const KEY& tKey):
m_dwLevel(0x00),
m_dwWeight(0x00),
m_tData(tData),
m_tKey(tKey),
m_pParent(NULL),
m_pChildLeft(NULL),
m_pChildRight(NULL)
{

}


/**
* Destruction
*
* @param
* @return
* @note
* @attention 
*/
template<typename T, typename KEY> 
AL_TreeNodeBinSearchSeq<T, KEY>::~AL_TreeNodeBinSearchSeq()
{
	//it doesn't matter to clear the pointer or not.
	Clear();
}

/**
* GetLevel
*
* @param
* @return	DWORD
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
* @attention 
*/
template<typename T, typename KEY> DWORD 
AL_TreeNodeBinSearchSeq<T, KEY>::GetLevel() const
{
	return m_dwLevel;
}

/**
* SetLevel
*
* @param	DWORD dwLevel <IN>
* @return	
* @note Node levels: starting from the root to start defining the root of the first layer, the root node is a sub-layer 2, and so on;	
* @attention 
*/
template<typename T, typename KEY> VOID 
AL_TreeNodeBinSearchSeq<T, KEY>::SetLevel(DWORD dwLevel)
{
	m_dwLevel = dwLevel;
}

/**
* GetWeight
*
* @param
* @return	DWORD
* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
* @attention only be used in Huffman tree...
*/
template<typename T, typename KEY> DWORD 
AL_TreeNodeBinSearchSeq<T, KEY>::GetWeight() const
{
	return m_dwWeight;
}

/**
* SetWeight
*
* @param	DWORD dwWeight <IN>
* @return	
* @note If the tree node is assigned a numerical value has some meaning, then this value is called the node weights
* @attention only be used in Huffman tree...
*/
template<typename T, typename KEY> VOID 
AL_TreeNodeBinSearchSeq<T, KEY>::SetWeight(DWORD dwWeight)
{
	m_dwWeight = dwWeight;
}

/**
* GetData
*
* @param
* @return	T
* @note 
* @attention 
*/
template<typename T, typename KEY> T 
AL_TreeNodeBinSearchSeq<T, KEY>::GetData() const
{
	return m_tData;
}

/**
* SetData
*
* @param	const T& tData <IN>
* @return	
* @note 
* @attention 
*/
template<typename T, typename KEY> VOID 
AL_TreeNodeBinSearchSeq<T, KEY>::SetData(const T& tData)
{
	m_tData = tData;
}

/**
* GetKey
*
* @param
* @return	KEY
* @note 
* @attention 
*/
template<typename T, typename KEY> KEY 
AL_TreeNodeBinSearchSeq<T, KEY>::GetKey() const
{
	return m_tKey;
}

/**
* SetData
*
* @param	const KEY& tKey <IN>
* @return	
* @note 
* @attention 
*/
template<typename T, typename KEY> VOID 
AL_TreeNodeBinSearchSeq<T, KEY>::SetKey(const KEY& tKey)
{
	m_tKey = tKey;
}

/**
* GetParent
*
* @param	
* @return	AL_TreeNodeBinSearchSeq<T, KEY>*	
* @note parent node pointer, not to manager memory
* @attention 
*/
template<typename T, typename KEY> AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeNodeBinSearchSeq<T, KEY>::GetParent() const
{
	return m_pParent;
}

/**
* SetParent
*
* @param	DWORD dwIndex <IN>
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pParent <IN>
* @return	BOOL
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the index (from the left of parent's child ) [0x00: left child, 0x01: right child]
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::SetParent(DWORD dwIndex, AL_TreeNodeBinSearchSeq<T, KEY>* pParent)
{
	if (NULL == pParent) {
		return FALSE;
	}

	BOOL  bSetParent = FALSE;
	bSetParent = pParent->Insert(dwIndex, this);
	if (TRUE == bSetParent) {
		//current node insert to the parent successfully
		if (NULL != m_pParent) {
			//current node has parent
			if (FALSE == m_pParent->Remove(this)) {
				return FALSE;
			}
		}
		m_pParent = pParent;
	}
	return bSetParent;
}

/**
* SetParentLeft
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pParent <IN>
* @return	
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the left (from the left of parent's child )
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::SetParentLeft(AL_TreeNodeBinSearchSeq<T, KEY>* pParent)
{
	return SetParent(0x00, pParent);
}

/**
* SetParentRight
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pParent <IN>
* @return	
* @note parent node pointer, not to manager memory
* @attention as the child to set the parent at the right (from the right of parent's child )
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::SetParentRight(AL_TreeNodeBinSearchSeq<T, KEY>* pParent)
{
	return SetParent(0x01, pParent);
}

/**
* Insert
*
* @param	DWORD dwIndex <IN>
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild <IN> 
* @return	BOOL
* @note inset the const AL_TreeNodeBinSearchSeq<T, KEY>*  into the child notes at the position [0x00: left child, 0x01: right child]
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::Insert(DWORD dwIndex, AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild)
{
	if (0x01 < dwIndex || NULL == pInsertChild) {
		return FALSE;
	}
	
	if (this == pInsertChild) {
		//itself
		return FALSE;
	}

	BOOL  bInsert = FALSE;
	if (0x00 == dwIndex && NULL == m_pChildLeft) {
		//left and the child left not exist
		m_pChildLeft = pInsertChild;
		bInsert = TRUE;
	}
	else if (0x01 == dwIndex && NULL == m_pChildRight) {
		//right and the child right not exist
		m_pChildRight = pInsertChild;
		bInsert = TRUE;
	}
	else {
		//no case
		bInsert = FALSE;
	}

	if (TRUE == bInsert) {
		if (GetLevel()+1 != pInsertChild->GetLevel()) {
			//deal with the child level
			INT iLevelDiff = pInsertChild->GetLevel() - GetLevel();
			pInsertChild->SetLevel(GetLevel()+1);

			AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*> listDescendant;
			if (TRUE == pInsertChild->GetDescendant(listDescendant)) {
				//insert child node has descendant
				AL_TreeNodeBinSearchSeq<T, KEY>* pDescendant = NULL;
				for (DWORD dwCnt=0x00; dwCnt<listDescendant.Length(); dwCnt++) {
					if (TRUE == listDescendant.Get(dwCnt, pDescendant)) {
						if (NULL != pDescendant) {
							//set child level
							pDescendant->SetLevel(pDescendant->GetLevel()-iLevelDiff+1);
						}
						else {
							//error
							return FALSE;
						}
					}
					else {
						//error
						return FALSE;
					}
				}
			}		
		}
		//child node insert to the current successfully
		pInsertChild->m_pParent = this;
	}
	return bInsert;
}

/**
* InsertLeft
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild <IN> 
* @return	BOOL
* @note inset the const AL_TreeNodeBinSearchSeq<T, KEY>*  into the child notes at the left
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::InsertLeft(AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild)
{
	return Insert(0x00, pInsertChild);
}

/**
* InsertRight
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild <IN> 
* @return	BOOL
* @note inset the const AL_TreeNodeBinSearchSeq<T, KEY>*  into the child notes at the right
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::InsertRight(AL_TreeNodeBinSearchSeq<T, KEY>* pInsertChild)
{
	return Insert(0x01, pInsertChild);
}

/**
* RemoveParent
*
* @param
* @return	BOOL
* @note remove the parent note
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::RemoveParent()
{
	BOOL bRemove = FALSE;
	//don't care the parent node exist or not
	m_pParent = NULL;
	bRemove = TRUE;
	/*
	if (NULL != m_pParent) {
		m_pParent = NULL;
		bRemove = TRUE;
	}
	*/
	return bRemove;
}

/**
* Remove
*
* @param	AL_TreeNodeBinSearchSeq<T, KEY>* pRemoveChild <IN>
* @return	BOOL
* @note remove the notes in the child
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::Remove(AL_TreeNodeBinSearchSeq<T, KEY>* pRemoveChild)
{
	BOOL bRemove = FALSE;
	if (m_pChildLeft == pRemoveChild) {
		m_pChildLeft = NULL;
		bRemove = TRUE;
	}
	else if (m_pChildRight ==  pRemoveChild) {
		m_pChildRight = NULL;
		bRemove = TRUE;
	}
	else {
		bRemove = FALSE;
	}
	return bRemove;
}

/**
* Remove
*
* @param	DWORD dwIndex <IN>
* @return	BOOL
* @note remove the child notes at the position [0x00: left child, 0x01: right child]
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::Remove(DWORD dwIndex)
{
	AL_TreeNodeBinSearchSeq<T, KEY>* pRemoveChild = NULL;
	if (0x00 == dwIndex) {
		pRemoveChild = m_pChildLeft;
	}
	else if (0x01 == dwIndex) {
		pRemoveChild = m_pChildRight;
	}
	else {
		return FALSE;
	}

	return Remove(pRemoveChild);
}

/**
* RemoveLeft
*
* @param
* @return	BOOL
* @note remove the child notes at the left
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::RemoveLeft()
{
	return Remove(m_pChildLeft);
}

/**
* RemoveRight
*
* @param
* @return	BOOL
* @note remove the child notes at the right
* @attention
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::RemoveRight()
{
	return Remove(m_pChildRight);
}

/**
* GetChildLeft
*
* @param	
* @return	AL_TreeNodeBinSearchSeq<T, KEY>*
* @note 
* @attention
*/
template<typename T, typename KEY> AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeNodeBinSearchSeq<T, KEY>::GetChildLeft() const
{
	return m_pChildLeft;
}

/**
* GetChildRight
*
* @param	
* @return	AL_TreeNodeBinSearchSeq<T, KEY>*
* @note 
* @attention
*/
template<typename T, typename KEY> AL_TreeNodeBinSearchSeq<T, KEY>* 
AL_TreeNodeBinSearchSeq<T, KEY>::GetChildRight() const
{
	return m_pChildRight;
}

/**
* GetDegree
*
* @param
* @return	DWORD
* @note degree node: A node of the subtree containing the number is called the node degree;
* @attention 
*/
template<typename T, typename KEY> DWORD 
AL_TreeNodeBinSearchSeq<T, KEY>::GetDegree() const
{
	DWORD dwDegree = 0x00;
	if (NULL != m_pChildLeft) {
		dwDegree++;
	}
	if (NULL != m_pChildRight) {
		dwDegree++;
	}

	return dwDegree;
}

/**
* IsLeaf
*
* @param
* @return	BOOL
* @note leaf nodes or terminal nodes: degree 0 are called leaf nodes;
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::IsLeaf() const
{
	return (0x00 == GetDegree()) ? TRUE:FALSE;
}

/**
* IsBranch
*
* @param
* @return	BOOL
* @note non-terminal node or branch node: node degree is not 0;
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::IsBranch() const
{
	return (0x00 != GetDegree()) ? TRUE:FALSE;
}

/**
* IsParent
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>* pChild <IN>
* @return	BOOL
* @note parent node or the parent node: If a node contains a child node, this node is called its child 
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::IsParent(const AL_TreeNodeBinSearchSeq<T, KEY>* pChild) const
{
	if (NULL ==  pChild) {
		return FALSE;
	}
	// 	AL_TreeNodeBinSearchSeq<T, KEY>* pCompare = NULL;
	// 	for (DWORD dwCnt=0x00; dwCnt<GetDegree(); dwCnt++) {
	// 		if (TRUE == m_listChild.Get(pCompare, dwCnt)) {
	// 			if (pCompare == pChild) {
	// 				//find the child
	// 				return TRUE;
	// 			}
	// 		}
	// 	}
	// 	return FALSE;

	if (this == pChild->m_pParent) {
		return TRUE;
	}
	return FALSE;
}

/**
* GetSibling
*
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling <OUT>
* @return	BOOL
* @note sibling nodes: nodes with the same parent node is called mutual sibling;
* @attention 
*/
template<typename T, typename KEY> BOOL
AL_TreeNodeBinSearchSeq<T, KEY>::GetSibling(AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listSibling) const
{
	BOOL bSibling = FALSE;
	if (NULL == m_pParent) {
		//not parent node
		return bSibling;
	}

	listSibling.Clear();

	AL_TreeNodeBinSearchSeq<T, KEY>* pParentChild = GetChildLeft();
	if (NULL != pParentChild) {
		if (pParentChild != this) {
			//not itself
			listSibling.InsertEnd(pParentChild);
			bSibling = TRUE;
		}
	}

	pParentChild = GetChildRight();
	if (NULL != pParentChild) {
		if (pParentChild != this) {
			//not itself
			listSibling.InsertEnd(pParentChild);
			bSibling = TRUE;
		}
	}

	return bSibling;
}

/**
* GetAncestor
*
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention 
*/
template<typename T, typename KEY> BOOL
AL_TreeNodeBinSearchSeq<T, KEY>::GetAncestor(AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listAncestor) const
{
	if (NULL == m_pParent) {
		//not parent node
		return FALSE;
	}

	listAncestor.Clear();
	AL_TreeNodeBinSearchSeq<T, KEY>* pParent = m_pParent;
	while (NULL != pParent) {
		listAncestor.InsertEnd(pParent);
		pParent = pParent->m_pParent;
	}
	return TRUE;
}

/**
* GetDescendant
*
* @param	AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant <OUT>
* @return	BOOL
* @note ancestor node: from the root to the node through all the nodes on the branch;
* @attention 
*/
template<typename T, typename KEY> BOOL 
AL_TreeNodeBinSearchSeq<T, KEY>::GetDescendant(AL_ListSeq<AL_TreeNodeBinSearchSeq<T, KEY>*>& listDescendant) const
{
	if (TRUE == IsLeaf()) {
		//child node
		return FALSE;
	}
	
	listDescendant.Clear();
	AL_TreeNodeBinSearchSeq<T, KEY>* pDescendant = GetChildLeft();
	if (NULL != pDescendant) {
		listDescendant.InsertEnd(pDescendant);
	}

	pDescendant = GetChildRight();
	if (NULL != pDescendant) {
		listDescendant.InsertEnd(pDescendant);
	}

	//loop the all node in listDescendant
	DWORD dwDescendantLoop = 0x00;
	AL_TreeNodeBinSearchSeq<T, KEY>* pDescendantLoop = NULL;
	while (TRUE == listDescendant.Get(dwDescendantLoop, pDescendant)) {
		dwDescendantLoop++;
		if (NULL != pDescendant) {
			pDescendantLoop = pDescendant->GetChildLeft();
			if (NULL != pDescendantLoop) {
				listDescendant.InsertEnd(pDescendantLoop);
			}

			pDescendantLoop = pDescendant->GetChildRight();
			if (NULL != pDescendantLoop) {
				listDescendant.InsertEnd(pDescendantLoop);
			}
		}
		else {
			//error
			return FALSE;
		}
	}
	return TRUE;
}

/**
* Clear
*
* @param
* @return	VOID
* @note
* @attention 
*/
template<typename T, typename KEY> VOID 
AL_TreeNodeBinSearchSeq<T, KEY>::Clear()
{
	m_dwLevel = 0x00;
	m_dwWeight = 0x00;
	m_pParent = NULL;
	m_pChildLeft = NULL;
	m_pChildRight = NULL;
}

/**
*Assignment
*
* @param	const AL_TreeNodeBinSearchSeq<T, KEY>& cAL_TreeNodeBinSearchSeq
* @return	AL_TreeNodeBinSearchSeq<T, KEY>&
*/
template<typename T, typename KEY> AL_TreeNodeBinSearchSeq<T, KEY>& 
AL_TreeNodeBinSearchSeq<T, KEY>::operator = (const AL_TreeNodeBinSearchSeq<T, KEY>& cAL_TreeNodeBinSearchSeq)
{
	m_dwLevel = cAL_TreeNodeBinSearchSeq.m_dwLevel;
	m_dwWeight = cAL_TreeNodeBinSearchSeq.m_dwWeight;
	m_tData = cAL_TreeNodeBinSearchSeq.m_tData;
	m_tKey = cAL_TreeNodeBinSearchSeq.m_tKey;
	m_pParent = cAL_TreeNodeBinSearchSeq.m_pParent;
	m_pChildLeft = cAL_TreeNodeBinSearchSeq.m_pChildLeft;
	m_pChildRight = cAL_TreeNodeBinSearchSeq.m_pChildRight;
	return *this;
}
#endif // CXX_AL_TREENODEBINSEARCHSEQ_H
/* EOF */
